package com.hyacinth.concurrent;

import java.io.Serializable;
import java.util.AbstractList;
import java.util.concurrent.atomic.AtomicReference;
import java.util.concurrent.atomic.AtomicReferenceArray;

/**
 * @author zhangfb
 * @version 1.0.0.1
 * @since JDK 1.8
 */
public class LockFreeVector<E> extends AbstractList<E> implements Serializable {
    private static final long serialVersionUID = 6858407619379520391L;

    private static final int MARK_FIRST_BIT = 0x80000000;

    private static final boolean DEBUG = false;  // 是否打印桶中元素信息

    private static final int N_BUCKET = 30;

    private static final int FIRST_BUCKET_SIZE = 8;

    private static final int ZERO_NUM_FIRST = Integer.numberOfLeadingZeros(FIRST_BUCKET_SIZE);

    private final AtomicReferenceArray<AtomicReferenceArray<E>> buckets;

    private AtomicReference<Descriptor<E>> descriptor;

    public LockFreeVector() {
        // 初始化桶，初始化大小32
        buckets = new AtomicReferenceArray<AtomicReferenceArray<E>>(N_BUCKET);
        buckets.set(0, new AtomicReferenceArray<E>(FIRST_BUCKET_SIZE));
        descriptor = new AtomicReference<Descriptor<E>>(new Descriptor<E>(0, null));
    }

    /**
     * 推入元素
     * @param e
     */
    public void pushBack(E e) {
        Descriptor<E> desc;
        Descriptor<E> newd;
        do {
            desc = descriptor.get();
            // 先执行写入，防止上一个线程设置完descriptor后，还没来得及写入，预防操作
            desc.comparedWrite();

            // 确定桶的位置
            int pos = desc.size + FIRST_BUCKET_SIZE;
            int zeroNumPos = Integer.numberOfLeadingZeros(pos);
            int bucketId = ZERO_NUM_FIRST - zeroNumPos;
            if (buckets.get(bucketId) == null) {
                // 如果bucketId对应的桶为空，则创建一个新桶，桶的大小为前一个桶的2倍
                // 扩容
                int newLen = 2 * buckets.get(bucketId -1).length();
                if (DEBUG) {
                    System.out.println("New Length is:" + newLen);
                }
                // 创建新桶，大小为newLen
                buckets.compareAndSet(bucketId, null, new AtomicReferenceArray<E>(newLen));
            }

            // 计算bucketId对应的桶中存放数据的下标
            int idx = (MARK_FIRST_BIT >>> zeroNumPos) ^ pos;
            // 创建元素执行器
            newd = new Descriptor<E>(desc.size + 1, new WriteDescriptor<E>(buckets.get(bucketId), idx, null, e));

        } while (!descriptor.compareAndSet(desc, newd));
        // CAS写入元素
        descriptor.get().comparedWrite();
    }

    public E popBack() {
        Descriptor<E> desc;
        Descriptor<E> newd;
        E elem;
        do {
            desc = descriptor.get();
            desc.comparedWrite();

            int pos = desc.size + FIRST_BUCKET_SIZE - 1;
            int bucketInd = Integer.numberOfLeadingZeros(FIRST_BUCKET_SIZE) - Integer.numberOfLeadingZeros(pos);
            int idx = Integer.highestOneBit(pos) ^ pos;
            elem = buckets.get(bucketInd).get(idx);
            newd = new Descriptor<E>(desc.size - 1, null);
        } while (!descriptor.compareAndSet(desc, newd)); // CAS to complete all
        // steps if succeed

        return elem;
    }

    @Override
    public E get(int index) {
        // 定位桶的位置
        int pos = index + FIRST_BUCKET_SIZE;
        int zeroNumPos = Integer.numberOfLeadingZeros(pos);
        int bucketId = ZERO_NUM_FIRST - zeroNumPos;
        // 定位桶中元素的下标
        int idx = (MARK_FIRST_BIT >>> zeroNumPos) ^ pos;
        return buckets.get(bucketId).get(idx);
    }

    @Override
    public E set(int index, E e) {
        int pos = index + FIRST_BUCKET_SIZE;
        int bucketInd = Integer.numberOfLeadingZeros(FIRST_BUCKET_SIZE)
                - Integer.numberOfLeadingZeros(pos);
        int idx = Integer.highestOneBit(pos) ^ pos;
        AtomicReferenceArray<E> bucket = buckets.get(bucketInd);
        while (true) {
            E oldV = bucket.get(idx);
            if (bucket.compareAndSet(idx, oldV, e))
                return oldV;
        }
    }

    @Override
    public boolean add(E object) {
        pushBack(object);
        return true;
    }

    public void reserve(int newSize) {
        int size = descriptor.get().size;
        int pos = size + FIRST_BUCKET_SIZE - 1;
        int i = Integer.numberOfLeadingZeros(FIRST_BUCKET_SIZE)
                - Integer.numberOfLeadingZeros(pos);
        if (i < 1)
            i = 1;

        int initialSize = buckets.get(i - 1).length();
        while (i < Integer.numberOfLeadingZeros(FIRST_BUCKET_SIZE)
                - Integer.numberOfLeadingZeros(newSize + FIRST_BUCKET_SIZE - 1)) {
            i++;
            initialSize *= FIRST_BUCKET_SIZE;
            buckets.compareAndSet(i, null, new AtomicReferenceArray<E>(initialSize));
        }
    }

    @Override
    public int size() {
        return descriptor.get().size;
    }

    /**
     * 删除桶中下标对应的元素
     * @param index 下标
     * @return 元素
     */
    public E delete(int index) {
        Descriptor<E> desc;
        Descriptor<E> newd;
        E elem = null;
        do {
            desc = descriptor.get();
            desc.comparedWrite();

            // 定位桶的位置
            int pos = index + FIRST_BUCKET_SIZE;
            int zeroNumPos = Integer.numberOfLeadingZeros(pos);
            int bucketId = ZERO_NUM_FIRST - zeroNumPos;
            AtomicReferenceArray<E> bucket = buckets.get(bucketId);
            if (bucket != null) {
                // 定位桶中元素的下标
                int idx = (MARK_FIRST_BIT >>> zeroNumPos) ^ pos;
                elem = bucket.get(idx);
                bucket.compareAndSet(idx, elem, null);
            }
            newd = new Descriptor<E>(desc.size - 1, null);
        } while (!descriptor.compareAndSet(desc, newd)); // CAS to complete all
        // steps if succeed

        return elem;
    }

    static class Descriptor<E> {
        public int size;
        volatile WriteDescriptor<E> writer;

        public Descriptor(int size, WriteDescriptor<E> writer) {
            this.size = size;
            this.writer = writer;
        }

        public void comparedWrite() {
            WriteDescriptor<E> w = writer;
            if (w != null) {
                w.doIt();
                writer = null;
            }
        }
    }

    /**
     * 写执行器，执行最终写入操作
     * CAS
     * @param <E>
     */
    static class WriteDescriptor<E> {
        public E oldV;
        public E newV;
        public int addInd;
        public AtomicReferenceArray<E> addr;

        public WriteDescriptor(AtomicReferenceArray<E> addr, int addInd, E oldV, E newV) {
            this.oldV = oldV;
            this.newV = newV;
            this.addInd = addInd;
            this.addr = addr;
        }

        public void doIt() {
            addr.compareAndSet(addInd, oldV, newV);
        }
    }

    public static void main(String[] args) {
        int initP = 8;
        int pos = initP + FIRST_BUCKET_SIZE;
        int zeroNumPos = Integer.numberOfLeadingZeros(pos);
        int idx = (MARK_FIRST_BIT >>> zeroNumPos) ^ pos;

        // 十六进制：0x80000000
        // 二进制
        //   源码： 10000000000000000000000000000000
        //   反码： 11111111111111111111111111111111  --- 负数的反码，首位不变，其他为按位取反；正数按位取反
        //   补码：110000000000000000000000000000000  --- 负数的补码是其反码+1，正数的补码与原码相同
        // 十进制   -2147483648 --- 2 << 31 - 1
        System.out.println(MARK_FIRST_BIT);
        System.out.println(idx);
    }
}
